class BasicPathGenerator:
    """基本路径生成器，使用深度优先搜索算法找出所有路径"""

    def __init__(self, adjacency_matrix):
        self.adj_matrix = adjacency_matrix
        self.paths = []
        self.max_path_length = 30  # 最大路径长度限制

    def find_all_paths(self, start=2, end=None, max_depth=30):
        """
        使用DFS查找从起点到终点的所有路径
        :param start: 起始节点
        :param end: 终止节点
        :param max_depth: 最大搜索深度
        :return: 所有有效路径列表
        """
        if end is None:
            end = len(self.adj_matrix) - 1

        self.max_path_length = max_depth
        visited_count = [0] * len(self.adj_matrix)
        path = []
        self.dfs(start, end, path, visited_count, max_depth)

        # 去重
        unique_paths = []
        seen = set()
        for p in self.paths:
            key = tuple(p)
            if key not in seen:
                seen.add(key)
                unique_paths.append(p)
        return unique_paths

    def dfs(self, current, end, path, visited_count, remaining_depth):
        """
        深度优先搜索实现
        :param current: 当前节点
        :param end: 目标节点
        :param path: 当前路径
        :param visited_count: 访问计数数组
        :param remaining_depth: 剩余搜索深度
        """
        if remaining_depth <= 0:
            return

        # 更新访问状态和路径
        visited_count[current] += 1
        path.append(current)

        # 如果到达目标节点
        if current == end:
            self.paths.append(list(path))
        else:
            for neighbor, weight in enumerate(self.adj_matrix[current]):
                if weight > 0:
                    # 添加简单路径判断，避免无限循环
                    if visited_count[neighbor] < 3:  # 同一节点最多访问3次
                        self.dfs(neighbor, end, path, visited_count, remaining_depth - 1)

        path.pop()
        visited_count[current] -= 1

    def simplify_paths(self, paths):
        """简化路径表示，移除冗余节点"""
        simplified_paths = []
        for path in paths:
            simplified = []
            for i, node in enumerate(path):
                # 只保留关键节点（跳过连续编号的普通执行节点）
                if i == 0 or i == len(path) - 1 or not (path[i - 1] + 1 == node and node + 1 == path[i + 1]):
                    simplified.append(node)
            simplified_paths.append(simplified)
        return simplified_paths
